package shujujiegou;

import java.util.Random;



public class SkipList2<T> {
	public Node2<T> head;
	public Node2<T> first;
	public Node2<T> last;
	public int length;
	public int height;//1��ʼ
	public Random r = new Random();
	
	public SkipList2() {
		last = new Node2<T>();
		last.key = Integer.MAX_VALUE;
		first = new Node2<T>();
		first.key = Integer.MIN_VALUE;
		first.next[0] = last;
		first.next[1] = last;
		first.next[2] = last;
		first.next[3] = last;
		head = first;
		height = 1;
	}
	public void add(int key, T value){
		Node2<T> pervNode = findPrev(key);
		length++;
		//��ȡ�µĸ߶�
		height = getNewHeightBylength(length);
		//����½ڵ�
		addNewNode(key, value, pervNode);
		
	}
	//����½ڵ�
	private void addNewNode(int key, T value, Node2<T> pervNode) {
		Node2<T> newNode = new Node2<T>();
		newNode.key = key;
		newNode.value = value;
		
		
		//�½ڵ�nextָ���һ���ڵ�
		newNode.next[0] = pervNode.next[0];
		//��height-1�λ������Ӳ���
		for(int i=0, j=1;i<height-1;i++){
			if(r.nextBoolean()) {
				newNode.next[j++] = pervNode.next[0];
			}
		}
		//ǰһ���ڵ�next[]��ָ���½ڵ�
		for(Node2<T> next : pervNode.next) {
			next = newNode;
		}
	}
	
	//��ѯ��key��ǰһ���ڵ�
	/*
	 * �������
	 * ��ǰ�ڵ�ĺ�һ���ڵ�key���������key�Ҹ߶Ȳ���1  ��ǰ�ڵ������ƶ���tHeight--
	 * ��ǰ�ڵ�ĺ�һ���ڵ�key���������key�Ҹ߶���1  ��ǰ�ڵ��key��ǰ�ڵ�
	 * ��ǰ�ڵ�ĺ�һ���ڵ�keyС�������key    ��ǰ�ڵ�����ƶ�
	 */
	private Node2<T> findPrev(int key) {
		Node2<T> tNode = first;
		int tHeight = height;
		while(true) {
			if(tNode.next[tHeight-1].key == key) {
				return null;
			}
			if(tNode.next[tHeight-1].key > key) {
				if(tHeight == 1) {
					return tNode;
				} else {
					tHeight--;
				}
			}
			if(tNode.next[tHeight-1].key < key) {
				tNode = tNode.next[tHeight-1];
			}
			
		}
		
		
	}
	
	
	
	//lengthΪ2ʱ->2��   4->3��   8->4��
	private int getNewHeightBylength(int length) {
		return (int) (log2(length)+1);
	}
	private double log2(int a) {
		return Math.log(a)/Math.log(2);
	}
	
	
}
class Node2<T> {
	public Node2<T>[] next;//�±��ʾ�ڼ���  ָ����һ���ڵ�
	public int key;
	public T value;
	public Node2() {
		next = new Node2[10];
	}
	
	
}